1. Field of the Invention
The present invention relates to a cooperative distributed problem solver in which a plurality of agents cooperate to solve a problem.
2. Description of the Related Art
A cooperative distributed problem solver has been known as a solver in which a plurality of agents cooperate to solve a problem which is difficult for a single problem solver to solve. In this case, although an agent means a problem solver, each problem solver constituting a cooperative distributed problem solver will be specifically called an agent in order to distinguish it from a single problem solver. Each agent constituting this cooperative distributed problem solver performs a problem solving in cooperation with other agents. In this operation, agents suitable for cooperation must be selected. For this selection, each agent requires information about other agents.
Conventional methods of selecting agents are: a mutual selection method in which agents requiring cooperation and required agents select each other on the basis of their own criteria; and a selection method in which a management agent for managing pieces of information about all the agents is independently prepared, and agents are selected on the basis of information which is transmitted from the management agent in response to a request for information required for selection.
A typical example of the former mutual selection is called contract net protocol, which is disclosed in Reid G. Smith, "The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver", Reading in Distributed Artificial Intelligence, pp. 357-366. In the contract net protocol, an agent requiring cooperation (to be referred to as a "manager" hereinafter) informs the remaining agents constituting the cooperative distributed problem solver that it requires cooperation and performs selection of cooperative agents. That is, the agent performs broadcasting. Upon this broadcasting, agents capable of cooperation inform the manager that they can cooperate to solve the problem with the manager. That is, they submit bids as tenders. The manager evaluates the bids to select agents suitable for cooperation, and informs the selected agents that they are selected as cooperative agents. That is, the manager makes contracts. Subsequently, the manager performs a problem solving operation in cooperation with the selected agents. In this manner, according to the contract net protocol, each agent can perform selection by utilizing pieces of dynamic information about other agents.
In the latter selection method using the management agent, pieces of information required for the respective agents to select cooperative agents are concentratedly managed by the management agent. Each agent requiring other cooperative agents requests information required for the selection of cooperative agents from the management agent, and performs selection on the basis of the received information. Such a selection method is disclosed, as an example, in "System & Network Administration", chap 14, The Sun Yellow Pages Services (Sun Work Station Manual). According to this method, in communication between agents, information to be managed by the management agent is acquired, each agent requests information for the selection of cooperate agents from the management agent, and information is transmitted/received between agents which operate in cooperation. Therefore, an increase in communication amount between agents can be suppressed.
In the contract net protocol, however, exchange of information required for selection between agents by means of broadcasting and a bid is performed for every selection of cooperative agents, and broadcasting is performed with respect to all the agents. Therefore, the communication amount between agents upon solving a problem increases with an increase in the frequency of occasions demanding cooperation and the number of agents. In the selection method using the management agent, as the necessity for cooperation increases with an increase in the number of agents and the size of a problem, the amount of information to be managed by the management agent and the number of requests for information with respect to the management agent increase. Consequently, the load of the management agent increases. Since the load of the management agent exclusively increases, the processing performance of the management agent becomes a bottleneck. That is, the processing performance of the management agent limits the overall processing speed of the cooperative distributed problem solver. In addition, if the management agent is stopped, all the agents cannot select agents suitable for cooperation. For this reason, a plurality of management agents must be set, and a mechanism for maintaining the information matching between the management agents is newly required.